import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List <List<Integer>> ret = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        //固定i
        for(int i = 0 ; i < nums.length;){
            //固定j
            for(int j = i + 1;j<nums.length;){
                int left = j+1;
                int right = nums.length-1;
                while(left < right){
                    //防止溢出
                    if(nums[left]+nums[right] > (long)target-nums[j]-nums[i]){
                        right--;
                    }else if(nums[left]+nums[right] < target-nums[j]-nums[i]){
                        left++;
                    }else{
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        right--;
                        left++;
                        //去重left、right
                        while(right > left && nums[left] == nums[left-1]) left++;
                        while(right > left && nums[right] == nums[right+1]) right--;
                    }
                }
                //去重j
                j++;
                while(j < nums.length && nums[j] == nums[j-1]) j++;
            }
            //去重i
            i++;
            while(i<nums.length && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
}
